1. Field of the Invention
This invention relates generally to computers, and more particularly to computer program products and methods for causing a computer to function in a particular efficient fashion.
2. Description of the Related Art
Modern computers contain microprocessors, which are essentially the brains of the computer. In operation, the computer uses the microprocessor to run or execute a computer program.
The computer program might be written in a high-level computer language, such as Pascal or C or C++, using statements similar to English, which statements are then translated (by another program called a compiler) into numerous machine-language instructions. Or the program might be written in assembly language, and then translated (by another program called an assembler) into machine-language instructions. In practice, every computer language above assembly language is a high-level language. (See Computer Dictionary (Microsoft Press, 3rd ed. 1997) for definitions of terms such as high-level language, branch instruction, branch prediction, case statement, and pipelining used herein.)
A computer program contains numerous instructions, which tell the computer what precisely it must do, to achieve the desired goal of the program. The computer runs a particular computer program by executing the instructions contained in the program in sequential order.
One type of instruction frequently contained in a computer program is a branch instruction. Some programs contain many branch instructions. A branch instruction is an assembly or machine-level instruction that transfers control to an instruction other than the next instruction in sequence, usually based on some condition, that is, it transfers control if a specific condition is true or false. Branch instructions cause the microprocessor to jump forward or backward in the computer program instruction code, to a particular branch in the program where the next instruction to be executed is located.
Knowing where the next instruction to be executed is located is necessary for fetching and decoding that instruction. Pipelining is a method used in some microprocessors of fetching and decoding instructions in which, at any given time, several program instructions are in various stages of being fetched or decoded. Ideally, pipelining speeds execution time by insuring that the microprocessor does not have to wait for instructions; when it completes execution of one instruction, the next is ready and waiting in the pipeline. A pipeline is a technique in which the output of one process serves as input to a second, the output of the second process serves as input to a third, and so on. In order to have the next instruction that is to be executed ready and waiting in the pipeline, the microprocessor somehow must predict what that instruction will be.
Branch prediction is a technique used in some microprocessors to guess whether or not a branch will be taken in a program, and to fetch executable code from the appropriate location. When a branch instruction is executed, it and the next instruction executed are stored in a buffer. This information is used to predict which way the instruction will branch the next time it is executed. When the prediction is correct, the program executes efficiently. When the prediction is incorrect, program execution is slowed down by the need to retrieve the next instruction. Such incorrect predictions are sometimes called branch mispredictions.
Various high-level computer program languages, such as Pascal, C, and C++, use a type of control statement that executes one of several sets of instructions based on some key value. This type of control statement is sometimes called a switch statement or a case statement (both names are used interchangeably herein), and the key is sometimes called a selection key.
Case statements are used in evaluating situations that can have a number of different results. A case statement functions like a series of IF-THEN type of conditional statements (that is, if A, then do this; else if B, then do that; else . . . ). In a case evaluation, a variable (such as a number or a string of characters) is compared against one after another of a series of constants assigned by the programmer. The variable is the selection key, and each constant represents a different case and defines an action to be carried out. When the program finds a constant that matches the variable, it carries out whatever action is dictated by the case in which the match occurs.
In the C computer language, for example, the code for a case statement might look as set forth below, in which the variable is "selection.sub.-- key", and the constants are 3, 109, 12, and 63.
______________________________________ switch (selection.sub.-- key) case 3: /* action to perform when selection.sub.-- key is 3 */ case 109: /* action to perform when selection.sub.-- key is 109 */ case 12: /* action to perform when selection.sub.-- key is 12 */ case 63: /* action to perform when selection.sub.-- key is 63 */ default: /* action to perform when selection.sub.-- key does not match any alternative */ } ______________________________________
In this example, the cases are case 3, case 109, case 12, and case 63. The numbers 3, 109, 12, and 63 are sometimes called case values. The case values, and the case statement, are said to be sparse, if the maximum case value minus the minimum case value is much greater than the number of case values. In this example, the maximum case value (109) minus the minimum case value (3) is 106, which is much greater than the number of case values (4); consequently these cases and this case statement are sparse.
When the case statement is not sparse, an efficient technique, known as a jump table, can be constructed and used to achieve the intended results of the case statement. When the case statement is sparse jump tables are impractical; consequently other techniques are used. Two known commonly used techniques to implement a sparse case statement are the linear technique and the binary tree technique.
The linear technique for a case statement is, essentially, a linear sequence of compares and jump conditions for each case. FIG. 1 illustrates a linear prior art technique, and the code for the illustrated linear technique is set forth below. The number of instructions executed in the code for such a linear technique is directly proportional to the number of possible cases.
______________________________________ cmp selection.sub.-- key, 3 je action.sub.-- for.sub.-- 3 cmp selection.sub.-- key, 109 je action.sub.-- for.sub.-- 109 cmp selection.sub.-- key, 12 je action.sub.-- for.sub.-- 12 cmp selection.sub.-- key, 63 je action.sub.-- for.sub.-- 63 default.sub.-- action: ______________________________________
The binary tree technique for a case statement is, essentially, a tree-like arrangement of compares and jump conditions. FIG. 2 illustrates a binary tree prior art technique, and the code for the illustrated binary tree is set forth below. The number of instructions executed in the code for such a binary tree is directly proportional to the log (the logarithm to the base 2) of the number of cases.
______________________________________ cmp selection.sub.-- key, 12 jg right.sub.-- side je action.sub.-- for.sub.-- 12 cmp selection.sub.-- key, 3 jg action.sub.-- for.sub.-- 3 jmp default.sub.-- action right.sub.-- side: cmp selection.sub.-- key, 109 jg default.sub.-- action je action.sub.-- for.sub.-- 109 cmp selection.sub.-- key, 63 je action.sub.-- for.sub.-- 63 default.sub.-- action: ______________________________________
Each of these prior art techniques contain multiple branches and multiple branch instructions (the je and jg and jmp jump statements). Since, in general, the input data is random, it is difficult to predict these branches correctly. Consequently, branch misprediction in each of these techniques can result in slowing down the system. The more branches, the greater the likelihood of branch mispredictions, and the greater the likelihood of slowing down the computer system because of the need to retrieve the next instruction to be executed.
Thus, the present invention is directed to overcoming, or at least reducing, the effects of one or more of the problems mentioned above.